#define _CRT_SECURE_NO_WARNINGS

#include<stdio.h>
#include<stdlib.h>


 struct ListNode {
    int val;
    struct ListNode* next;
    
};

typedef struct ListNode ListNode;
struct ListNode* partition(struct ListNode* head, int x) {
    if (head == NULL || head->next == NULL)
        return head;
    ListNode* lessnewhead, * lessnewtail, * greaternewhead, * greaternewtail;
    lessnewhead = lessnewtail = (ListNode*)malloc(sizeof(ListNode));
    greaternewhead = greaternewtail = (ListNode*)malloc(sizeof(ListNode));
    ListNode* pcur = head;
    while (pcur)
    {
        if (pcur->val < x)
        {
            lessnewtail->next = pcur;
            lessnewtail = lessnewtail->next;
        }
        else
        {
            greaternewtail->next = pcur;
            greaternewtail = greaternewtail->next;
        }
        pcur = pcur->next;
    }
    greaternewtail->next = NULL;
    lessnewtail->next = greaternewhead->next;
    ListNode* ret = lessnewhead->next;
    free(lessnewhead);
    free(greaternewhead);
    lessnewhead = lessnewtail = greaternewhead = greaternewtail = NULL;
    return ret;
}



struct ListNode* reverseBetween(struct ListNode* head, int left, int right) {
    ListNode* newhead = (ListNode*)malloc(sizeof(ListNode));
    newhead->next = head;
    ListNode* prev = newhead;
    for (int i = 1; i < left; i++)
    {
        prev = prev->next;
    }
    ListNode* pcur = prev->next;
    for (int i = 0; i < right - left; i++)
    {
        ListNode* next = pcur->next;
        pcur->next = next->next;
        next->next = prev->next;
        prev->next = next;
    }
    return newhead->next;
}

struct ListNode* detectCycle(struct ListNode* head) {
    ListNode* slow, * fast;
    slow = fast = head;
    do
    {
        if (fast == NULL || fast->next == NULL)
            return NULL;
        else
        {
            slow = slow->next;
            fast = fast->next->next;
        }
    } while (fast != slow);
    fast = head;
    while (fast != slow)
    {
        slow = slow->next;
        fast = fast->next;
    }
    return fast;
}

void reorderList(struct ListNode* head) {
    if (head == NULL)
        return;
    ListNode* arr[40000];
    ListNode* pcur = head;
    int n = 0;
    while (pcur)
    {
        arr[n++] = pcur;
        pcur = pcur->next;
    }
    int i = 0, j = n - 1;
    while (i < j)
    {
        arr[i]->next = arr[j];
        i++;
        if (i == j)
            break;
        arr[j]->next = arr[i];
        j--;
    }
    arr[i]->next = NULL;
}

int main()
{
    ListNode* a, * b, * c, * d,*e;
    a = (ListNode*)malloc(sizeof(ListNode));
    b = (ListNode*)malloc(sizeof(ListNode));
    d = (ListNode*)malloc(sizeof(ListNode));
    c = (ListNode*)malloc(sizeof(ListNode));
    e = (ListNode*)malloc(sizeof(ListNode));
    a->val = NULL;
    b->val = 2;
    c->val = 3;
    d->val = 4;
    e->val = 5;
    a->next = b;
    b->next = c;
    c->next = d;
    d->next = e;
    e->next = NULL;
    detectCycle(a);
	return 0;
}